package 牛客_面试必刷.Month07.day08;

import java.util.Stack;

public class 链表相加 {
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        //这里不用排除head == null || head2 == null的情况
        //第一个链表全部入栈
        Stack<ListNode> stack1 = new Stack<>();
        while(head1 != null){
            stack1.push(head1);
            head1 = head1.next;
        }
        //第二个链表全部入栈
        Stack<ListNode> stack2 = new Stack<>();
        while(head2 != null){
            stack2.push(head2);
            head2 = head2.next;
        }
        //不用创建新的节点，建立一个标志位就可以
        ListNode head = null;
        int count = 0;
        while(!stack1.isEmpty()  || !stack2.isEmpty() || count > 0){
            int res = count;//记得加入进位
            if(!stack1.isEmpty())  res += stack1.pop().val;
            if(!stack2.isEmpty())  res += stack2.pop().val;
            count = res / 10;//这里是记录当前的节点内的进制情况
            ListNode node = new ListNode(res % 10);
            //然后就是拼接
            node.next = head;
            head = node;
        }
        return head;
    }
}
